Levin reduction

Definition

If $R_1$ and $R_2$ are search problems and $\mathscr{C}$ is a complexity class then a $\mathscr{C}$ Levin reduction of $R_1$ to $R_2$ consists of three functions $g_1, g_2, g_3 \in \mathscr{C}$ satisfying

• $g_1$ is a $\mathscr{C}$ Karp reduction of $L(R_1)$ to $L(R_2)$
• if $R_1(x,y)$ then $R_2(f(x),g(x,y)$
• if $R_2(f(x),z)$ then $R_1(x,h(x,z))$

May denote P Levin reduction as simply Levin reduction.

See also

• Karp reduction
• Cook reduction

References

1. https://planetmath.org/levinreduction
2. https://cs.stackexchange.com/questions/2689/is-karp-reduction-identical-to-levin-reduction